package geekstudy.week9;

import java.util.*;

/**
 *
 *
 * 51. N 皇后
 * https://leetcode-cn.com/problems/n-queens/
 *
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：4 ms, 在所有 Java 提交中击败了58.67% 的用户
 * 内存消耗：39.3 MB, 在所有 Java 提交中击败了14.57% 的用户
 *
 *
 *
 */
public class Week9NQueue {

    public List<List<String>> solveNQueue(int n) {
        List<List<String>> queueList = new ArrayList<List<String>>();
        int[] queueArray = new int[n];
        Arrays.fill(queueArray, -1);
        Set<Integer> columnSet = new HashSet<Integer>();
        Set<Integer> slashSet = new HashSet<Integer>();
        Set<Integer> backslashSet = new HashSet<Integer>();
        backtrack(queueList, queueArray, n, 0, columnSet, slashSet, backslashSet);

        return queueList;
    }

    public List<String> generateBoard(int[] queueArray, int n) {
        List<String> boardList = new ArrayList<String>();
        for(int size = 0; size < n; size++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queueArray[size]] = 'Q';
            boardList.add(new String(row));
        }

        return boardList;
    }

    public void backtrack(List<List<String>> queueList, int[] queueArray, int n, int row, Set<Integer> columnSet, Set<Integer> slashSet, Set<Integer> backslashSet) {
        if(row == n) {
            List<String> boardList = generateBoard(queueArray, n);
            queueList.add(boardList);
        } else {
            for(int size = 0; size < n; size++) {
                if(columnSet.contains(size)) {
                    continue;
                }
                int slash = row - size;
                if(slashSet.contains(slash)) {
                    continue;
                }
                int backslash = row + size;
                if(backslashSet.contains(backslash)) {
                    continue;
                }
                queueArray[row] = size;
                columnSet.add(size);
                slashSet.add(slash);
                backslashSet.add(backslash);
                backtrack(queueList, queueArray, n, row + 1, columnSet, slashSet, backslashSet);
                queueArray[row] = -1;
                columnSet.remove(size);
                slashSet.remove(slash);
                backslashSet.remove(backslash);
            }
        }
    }
}
